import java.util.Arrays;
import java.util.Stack;

/**
 * 排序算法
 */
class Solution{
    public void insertSort(int[] arr){
        //1.定义变量i,变量数组
        int i = 0;
        for(;i < arr.length;i++){
            //2.此时还需要定义一个变量j,完成【0，j】区间排序
            //因为是从后往前插入元素，需要考虑边界情况，j下标的元素
            //与前面的元素可交换的条件为 j > 0
            int j = i;
            while(j > 0){
                //j 下标的元素小于 j - 1 下标的元素
                if(arr[j] < arr[j - 1]){
                    int tem = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = tem;

                    //交换后j下标往前移
                    j--;
                }
                //如果已经有序，不需要交换,跳出循环
                else break;
            }
        }
    }

    public static void main1(String[] args) {
        Solution s = new Solution();
        int[] arr = {5,3,1,6,7,2,4};
        s.insertSort(arr);
        for(int x : arr) System.out.print(x + " ");
    }

    //希尔排序
    public void shellSort1(int[] arr){
        int len = arr.length;

        int gap = len / 2;

        while(gap >= 1){
            for (int i = 0; gap + i  < len; i++) {

               int tem = arr[gap + i];
                int j = i;
                //回退：如果j下标元素大于j + gap下标元素就覆盖
                for (; j >= 0 ; j-= gap) {
                    if(arr[j] > tem)
                        arr[j + gap] = arr[i];
                    else break;
                }
                //此时的j是小于0的，需要将i + gap位置的元素补齐
               arr[j + gap] = tem;
            }
            gap /= 2;
        }
    }
    public void shellSort1_1(int[] arr){
        int len = arr.length;

        int gap = len / 2;

        while(gap >= 1){
            for (int i = 0; gap + i  < len; i++) {
                if(arr[i] > arr[gap + i]){
                    int tem = arr[i];
                    arr[i] = arr[gap + i];
                    arr[gap + i] = tem;

                    //回退
                    for(int j = i - gap; j >= 0;j -= gap){
                        if(arr[j] > arr[j + gap]){
                            tem = arr[j];
                            arr[j] = arr[j + gap];
                            arr[j + gap] = tem;
                        }else break;
                    }
                }
            }
            gap /= 2;
        }
    }
    //法二：分组后具体的交换使用直接插入排序
    public void shellSort2(int[] arr){
        //1.判断排序数组的长度
        int len = arr.length;

        if(len == 1) return;

        //2.分组 按 / 2分组
        int gap = len;
        while(gap >= 1){
            gap /= 2;

            //定义区间
            int start = 0;//从 0 到 gap - 1
            int end = len - gap;//len - gap 到 len - 1
            int count = gap;//使循环执行gap次
            while(count > 0){
                insertSort1(arr,0,end);
                start++;
                end++;
                count--;
            }
        }
    }

    //直接插入排序
    private static void insertSort1(int[] arr,int start,int end){

        for(int i = start + 1;i <= end;i++){
            int tem = arr[i];
            int j = i - 1;
            for(;j >=0;j--){
                if(arr[j] > tem)
                    arr[j + 1] = arr[j];
                else break;
            }
            arr[j + 1] = tem;
        }
    }

    //选择排序
    public  void selectSort(int[] arr){
        int length = arr.length;

        for(int i = 0;i < length - 1;i++){
            int minIndex = i;
            for(int j = i+ 1;j < length;j++){
               if(arr[j] < arr[minIndex])
                   minIndex = j;
            }
            //交换
            int tem = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = tem;
        }
    }

    public static void main3(String[] args) {
        Solution s = new Solution();
        int[] arr = {3,77,2,2,66,80,102};
        s.selectSort(arr);
        for(int x : arr) System.out.print(x + " ");
    }

    //快速排序
    //1.Hoare法：选定一个基准值target，划分左右区间
    //先右遍历，找到不符合区间的值，后左遍历，找到不符合左边区间的值
    //交换，，最后交换基准值和left下标
    public void quickSort(int[] arr) {

       quickSort2(arr,0,arr.length - 1);

    }
    private int three_num_mid(int[] arr,int left,int right,int mid){

        if(arr[left] > arr[right]){
            if(arr[mid] > arr[left]) return left;
            else if(arr[right] > arr[mid]) return right;
            else return mid;
        }else{
            if(arr[mid] > arr[right]) return right;
            else if(arr[left] > arr[mid]) return left;
            else return mid;
        }
    }
    private void quickSort1(int[] arr,int left,int right){

        if(left >= right) return;

        if(right - left <= 15){
            Solution.insertSort1(arr,left,right);
        }

        int l = left,r = right;
        int mid = l + (r - l) / 2;
        int index = three_num_mid(arr,left,right,mid);
        int target = arr[index];
         arr[index] = arr[l];
         arr[l] = target;

        while (left < right) {
            //找到右边不大于target的值
            while (left < right && arr[right] > target) right--;
            //找到左边不小于target的值
            while (left < right && arr[left] <= target) left++;
            //找到了交换
            int tem = arr[left];
            arr[left] = arr[right];
            arr[right] = tem;
        }
        //基准值位置与当前left下标位置交换
        arr[l] = arr[left];
        arr[left] = target;

        //划分左区间和右区间
        quickSort1(arr,l,left - 1);
        quickSort1(arr,left + 1,r);
    }

    private void quickSort2(int[] arr,int left,int right){

        if(left >= right) return;

        int l = left,r = right;
        int mid = left + (right - left) /2 ;
        int target = three_num_mid(arr,l,r,mid);;

        while (left < right) {

            //找到右边不大于target的值
            while (left < right && arr[right] > target) right--;
            arr[left] = arr[right];

            //找到左边不小于target的值
            while (left < right && arr[left] <= target) left++;
            arr[right] = arr[left];
        }
        //当前left位置存放基准值
        arr[left] = target;

        //划分左区间和右区间
        quickSort2(arr,l,left - 1);
        quickSort2(arr,left + 1,r);
    }

    //快慢双指针：满足条件 arr[fast] <= target && arr[++slow] != arr[fast]交换
    public void quickSort3(int[] arr,int left,int right){

        if(left >= right) return;

        //1.定义快慢双指针
        int slow = left;
        int fast = slow + 1;

        //目标值
        int target = arr[left];

        //2.遍历数组
        while (fast <= right) {
            //交换：快指针指向元素小于等于目标值 并且 快慢双指针不相邻
            if(arr[fast] <= target && arr[++slow] != arr[fast]){
                int tem =  arr[slow];
                arr[slow] = arr[fast];
                arr[fast]= tem;
            }
            fast++;
        }
        //将目标值存放在慢指针位置
        arr[left] = arr[slow];
        arr[slow] = target;


        //递归左右区间
        quickSort3(arr,left,slow - 1);
        quickSort3(arr,slow + 1,right);
    }

    //使用栈，保存划分的区间
    public void quickSortNonr(int[] arr){
        //创建一个栈
        Stack<Integer> stack = new Stack<Integer>();

        //开始的区间：0 - arr.length - 1
        stack.push(0);
        stack.push(arr.length - 1);

        while(!stack.empty()){

            //出栈
            int right = stack.pop();
            int left = stack.pop();
            //判断是否区间合法
            if(left >= right) continue;

            //调用方法:此处的partition方法是在快慢双指针方法的基础上最后慢指针的值
            int index = partition(arr,left,right);

            //将左右区间范围入栈：先加入右，后加入左
            stack.push(index + 1);
            stack.push(right);

            stack.push(left);
            stack.push(index - 1);

        }
    }
    //快慢双指针：满足条件 arr[fast] <= target && arr[++slow] != arr[fast]交换
    public int partition(int[] arr,int left,int right){

        //1.定义快慢双指针
        int slow = left;
        int fast = slow + 1;

        //目标值
        int target = arr[left];

        //2.遍历数组
        while (fast <= right) {
            //交换：快指针指向元素小于等于目标值 并且 快慢双指针不相邻
            if(arr[fast] <= target && arr[++slow] != arr[fast]){
                int tem =  arr[slow];
                arr[slow] = arr[fast];
                arr[fast]= tem;
            }
            fast++;
        }
        //将目标值存放在慢指针位置
        arr[left] = arr[slow];
        arr[slow] = target;

        return slow;

    }



    public static void main4(String[] args) {
        Solution s = new Solution();
        int[] arr = {54,2,62,63,22,44,22,7,33,1001,1,2,233};
        s.quickSortNonr(arr);
        for(int x : arr) System.out.print(x + " ");
    }

    //归并排序
    public void mergerSort(int[] arr){
        mergerSort(arr,0,arr.length - 1);
    }
    public void mergerSort(int[] arr,int left,int right){
        if(right - left < 1) return;

        //划分左右区间
        int mid = left + (right - left) / 2;

        //递归划分左右区间
        mergerSort(arr,left,mid);
        mergerSort(arr,mid+1,right);

        /**
         * 可以在此处先排序划分的左右区间
         * 也可以在merger函数中在排序合并
         */

        //合并数组
        merger(arr,left,mid,right);
    }
    private void merger(int[] arr,int left,int mid,int right){

        //创建一个临时数组，大小为划分区间的长度
        int[] tem = new int[right - left + 1];

        int s1 = left;
        int e1 = mid;

        int s2 = mid + 1;
        int e2 = right;

        //合并数组
        int k = 0;//临时数组索引
        while(s1 <= e1 && s2 <= e2){

            if(arr[s1] <= arr[s2] ) tem[k++] = arr[s1++];

            else tem[k++] = arr[s2++];
        }

        //判断是否左区间还剩元素
        while(s1 <= e1) tem[k++] = arr[s1++];

        //判断是否右区间还剩元素
        while(s2 <= e2) tem[k++] = arr[s2++];

        //将临时数组拷贝到原数组
        for (int i = 0;i < tem.length;i++){
            arr[left++] = tem[i];
        }
    }

    public void mergerSortNonR(int[] arr){
        int gap = 1;
        while(gap < arr.length){
            for (int i = 0; i < arr.length; i += 2*gap) {
                int left =  i;

                int mid = left + gap - 1;
                if(mid >= arr.length) mid = arr.length - 1;

                int right = mid + gap;
                if(right >= arr.length) right = arr.length - 1;

                merger(arr,left,mid,right);
            }
            gap *= 2;
        }
    }

    public static void main6(String[] args) {
        int[] arr = {1002,20,221,456,65,33,11};
        Solution  s = new Solution();
        s.mergerSortNonR(arr);
        for(int x : arr) System.out.print(x + " ");
    }


    public static void main12(String[] args) {
        int[] arr = {53,2,1,3};
        Solution  s = new Solution();
        s.shellSort1(arr);
        for(int x : arr) System.out.println(x + " ");
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] arr = new int[10000];
        for(int i = 0;i < 10000;i++) arr[i] = 10000 - i;

        int[] arr1 = Arrays.copyOf(arr,arr.length);
        int[] arr2 = Arrays.copyOf(arr,arr.length);
        int[] arr3 = Arrays.copyOf(arr,arr.length);
        int[] arr4 = Arrays.copyOf(arr,arr.length);
        int[] arr5 = Arrays.copyOf(arr,arr.length);


        long s1 = System.currentTimeMillis();

        s.insertSort(arr);

        long e1 = System.currentTimeMillis();

        System.out.println("直接插入排序需要的时间：" + (e1 - s1));

        long s2 = System.currentTimeMillis();

        s.shellSort1(arr1);

        long e2 = System.currentTimeMillis();

        System.out.println("希尔排序的时间：" + (e2 - s2));

        long s3 = System.currentTimeMillis();

        s.quickSort(arr2);

        long e3 = System.currentTimeMillis();

        System.out.println("快速排序的时间：" + (e3 - s3));

        long s4 = System.currentTimeMillis();

        s.mergerSort(arr3);

        long e4 = System.currentTimeMillis();

        System.out.println("归并排序的时间：" + (e4 - s4));

        long s5 = System.currentTimeMillis();

        s.selectSort(arr4);

        long e5 = System.currentTimeMillis();

        System.out.println("选择排序的时间：" + (e5 - s5));

        long s6 = System.currentTimeMillis();

        Arrays.sort(arr5);

        long e6 = System.currentTimeMillis();

        System.out.println("idea系统排序的时间：" + (e6 - s6));
    }
}
